#include "main/utils.h"
using namespace std;

// 分治法
int maxArea(const vector<int> &vec, const int &begin, const int &end) {
  if (begin >= end) {
    return 0;
  }

  int lowest_idx = begin;
  for (int i = begin + 1; i < end; ++i) {
    if (vec[i] < vec[lowest_idx]) {
      lowest_idx = i;
    }
  }

  int area = vec[lowest_idx] * (end - begin);
  int area_left = maxArea(vec, begin, lowest_idx);
  int area_right = maxArea(vec, lowest_idx + 1, end);
  int max_area = area > area_left ? area : area_left;
  max_area = max_area > area_right ? max_area : area_right;
  return max_area;
}

// 单调栈法
int maxArea(const vector<int> &vec) {
  int max_area = 0;
  stack<int> help_stack;
  help_stack.push(-1);
  for (int i = 0; i < vec.size(); ++i) {
    while (help_stack.top() != -1 && vec[help_stack.top()] > vec[i]) {
      int top = help_stack.top();
      help_stack.pop();
      int  area = vec[top] * (i - help_stack.top() - 1);
      if (area > max_area) {
        max_area = area;
      }
    }
    help_stack.push(i);
  }
  while (help_stack.top() != -1) {
    int top = help_stack.top();
    help_stack.pop();
    int area = vec[top] * (vec.size() - help_stack.top() - 1);
    if (area > max_area) {
      max_area = area;
    }
  }
  return max_area;
}

int main() {
  vector<int> vec = {3, 2, 5, 4, 6, 1, 4, 2};
  int max_area = maxArea(vec, 0, vec.size());
  cout << max_area << endl;

  int max_area1 = maxArea(vec);
  cout << max_area1 << endl;

  return 0;
}
